# 这里有 n 个一样的骰子，每个骰子上都有 k 个面，分别标号为 1 到 k 。
#  给定三个整数 n , k 和 target ，返回可能的方式(从总共 kⁿ 种方式中)滚动骰子的数量，使正面朝上的数字之和等于 target 。
#  答案可能很大，你需要对 10⁹ + 7 取模 。
#
#  示例 1：
# 输入：n = 1, k = 6, target = 3
# 输出：1
# 解释：你扔一个有6张脸的骰子。
# 得到3的和只有一种方法。
#
#  示例 2：
# 输入：n = 2, k = 6, target = 7
# 输出：6
# 解释：你扔两个骰子，每个骰子有6个面。
# 得到7的和有6种方法1+6 2+5 3+4 4+3 5+2 6+1。
#
#  示例 3：
# 输入：n = 30, k = 30, target = 500
# 输出：222616187
# 解释：返回的结果必须是对 10⁹ + 7 取模。
from functools import lru_cache


class Solution:
    def numRollsToTarget2(self, n: int, k: int, target: int) -> int:
        """
        动态规划
        相当于从一个数组[1, 2, 3..., k]有放回的取 n 个数，求能是的取出和为 target 的取法(要看顺序)
        :param n:
        :param k:
        :param target:
        :return:
        """
        if target < n:
            return 0
        if n == target:
            return 1
        dp = [[0 for __ in range(target + 1)] for _ in range(n + 1)]  # dp[i][j] = m 表示前i个骰子能够得到的结果和为 j 的排列数为 m
        dp[0][0] = 1
        for i in range(1, n + 1):  # 一共有 n 个骰子
            for diceNum in range(1, k + 1):  # 每个骰子取值可能有 1-k
                for j in range(diceNum, target + 1):
                    dp[i][j] += dp[i - 1][j - diceNum]
        return dp[-1][-1] % (10 ** 9 + 7)

    def numRollsToTarget1(self, n: int, k: int, target: int) -> int:
        @lru_cache(None)
        # diceCount表示几个骰子，total表示目标值, dfs(diceCount, total)表示一共使用 diceCount 个骰子得到和为 total 的组合数(顺序有关)
        def dfs(diceCount: int, total: int) -> int:
            if diceCount < 0 or total < 0:
                return 0
            if diceCount == 0 and total == 0:
                return 1
            res = 0
            for diceNum in range(1, k + 1):
                res += dfs(diceCount - 1, total - diceNum)
            return res % (10 ** 9 + 7)

        return dfs(n, target) % (10 ** 9 + 7)

    def numRollsToTarget(self, n: int, k: int, target: int) -> int:
        return self.numRollsToTarget1(n, k, target)


if __name__ == "__main__":
    n, k, target = 2, 6, 7
    # n, k, target = 30, 30, 500
    print(Solution().numRollsToTarget(n, k, target))
